#include <iostream>
#include <cassert>
#include "Graph.h"
#include "Bag.h"
#include "AdjGraph.h"

using namespace std;

AdjGraph* getGraph(){
    int v = 13;
    int e = 13;
//    int e = 10;
    int vs[13][2] = {{0,5},{4,3},{0,1},{9,12},{6,4},{5,4},{0,2},{11,12},{9,10},{0,6},{7,8},{9,11},{5,3}};
//    int vs[10][2] = {{0,5},{4,3},{0,1},{9,12},{6,4},{0,2},{11,12},{9,10},{0,6},{7,8}};

    AdjGraph* graph = new AdjGraph(v);
    for (int i = 0; i < e; ++i) {
        graph->addEdge(vs[i][0],vs[i][1]);
    }
    return graph;
}

int testAdjGraph() {
    AdjGraph* graph = getGraph();
    graph->print();

    delete graph;
    return 0;
}

int testSearch(int source) {
    AdjGraph* graph = getGraph();
    DepthFirstSearch* sch = new DepthFirstSearch(graph,source);
    cout << "connect vertexs is: ";
    for (int j = 0; j < graph->V(); ++j) {
        if (sch->marked(j)) {
            cout << j << " ";
        }
    }
    cout << endl;

    if(sch->size() != graph->V()){
        cout<<"Not ";
    }
    cout<< "connected" <<endl;
    delete sch;
    delete graph;
}

int testCC() {
    AdjGraph* graph = getGraph();
    CC* cc = new DepthFirstCC(graph);

    int M = cc->count();
    cout<< M << " components"<<endl;

    Bag<int>* components = new Bag<int>[M];
    for (int i = 0; i < M; ++i) {
        components[i] = *(new Bag<int>());
    }

    for (int j = 0; j < graph->V(); ++j) {
        components[cc->id(j)].add(j);
    }

    for (int k = 0; k < M; ++k) {
        vector<int>* vector1 = components[k].getVector();
        int size = vector1->size();
        for (int j =0; j < size; ++j) {
            cout << (*vector1)[j] << " ";
        }
        cout<<endl;
        delete vector1;
    }


    delete[] components;
    delete cc;
    delete graph;
}

int testPaths(Paths*  dfp,AdjGraph* graph, int source) {
    for (int j = 0; j < graph->V(); ++j) {
        if (dfp->hasPathTo(j)) {
            cout<<source << " to "<<j<<": ";
            stack<int>* stack1 = dfp->pathTo(j);
            while(!stack1->empty()){
                cout<<stack1->top() << "->";
                stack1->pop();
            }
            delete stack1;
            cout << endl;
        }
    }

    delete dfp;
    delete graph;
}

int testPaths() {
    int source = 0;
    AdjGraph* graph = getGraph();
    AdjGraph* graph2 = getGraph();
    DepthFirstPaths*  dfp = new DepthFirstPaths(graph,source);
    BreadthFirstPaths*  bfs = new BreadthFirstPaths(graph2,source);

    cout<<"test DepthFirstPaths:";
    testPaths(dfp,graph,0);

    cout<<"test BreadthFirstPaths:";
    testPaths(bfs,graph2,0);

    delete graph;
    delete dfp;
    delete graph2;
    delete bfs;
    return 0;
}


int testCycle() {
    AdjGraph* graph = getGraph();
    Cycle* cycle = new DfsCycle(graph);

    cout<<"testCycle:";
    cout<< (cycle->hasCycle()?"have cycle":"don't have cycle") <<endl;

    delete graph;
    delete cycle;
    return 0;
}

int testTwoColors() {
    AdjGraph* graph = getGraph();
    TwoColor* colorable = new DfsTwoColor(graph);

    cout<<"testTwoColors:";
    cout<< (colorable->isBipartite()?"can be binary part":"can't be binary part")<<endl;

    delete graph;
    delete colorable;
    return 0;
}

int main() {
    testAdjGraph();//正确性测试
//    testSearch(7);//搜索连通分量测试，连通性测试
//    testPaths();//路径测试，包括深度优先和广度优先
//    testCC();//连通分量数量，点集合测试
//    testCycle();//含环测试
//    testTwoColors();//二分图测试
    return 0;
}